package greedyMind

import (
	"fmt"
	"math"
	"sort"
)

// 贪心算法应用--最多区间覆盖问题

//假设我们有 n 个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。
//我们从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？

type Sections [][2]int

func (section Sections) Len() int {
	return len(section)
}

func (section Sections) Less(i, j int) bool {
	return section[i][0] <= section[j][0] // 比较起始端点
}

func (section Sections) Swap(i, j int) {
	section[i], section[j] = section[j], section[i]
}

// maxRight = 10 // 区间的最右范围
// minLeft = 0   // 起始区间最左位置
// sections 区间序列
func SectionSelect(minLeft, maxRight int, sections Sections) Sections {
	var result Sections
	var t = 0 // sections 序列遍历起始位置
	sort.Sort(sections)
	fmt.Println("sections排序后")
	fmt.Println(sections)
	sectionSelect(t, minLeft, maxRight, sections, &result)

	return result
}

func sectionSelect(t, minLeft, maxRight int, sections Sections, result *Sections) {
	// t 表示左边界坐标
	if t >= len(sections)-1 { // 已经移动到区间的尾部
		return
	}

	curMinRight := math.MaxInt64 // 每次搜索区间的最小右边界
	curMinLeft := math.MaxInt64  // 每次搜索区间的最小左边界
	newLeft := minLeft
	for i := t; i < len(sections); i++ {
		// 在满足不超过区间范围情况下，优先选择距离当前起始点最近的区间，以此让区间个数最大化
		// 从左到右依次搜索最小区间
		if sections[i][0] >= minLeft && sections[i][1] <= maxRight {
			if sections[i][1] <= curMinRight {
				curMinRight = sections[i][1]
				curMinLeft = sections[i][0]
				t = i
				newLeft = sections[i][1] // 记录新左边界
			}
		}
	}
	// 有满足条件的
	if curMinLeft != math.MaxInt64 {
		minLeft = newLeft
		*result = append(*result, [2]int{curMinLeft, curMinRight})
		// 下一个区间最优解的起始位置至少为当前起始位置+1
		sectionSelect(t+1, minLeft, maxRight, sections, result)
	}
}
